/* File: weights.c
 * --------------------
 * Author: Albin Olausson & Stella Wallin
 * Last modified: 2014-04-15
 * Task: A recursive program that determines
 * what weights that can be measured depending on 
 * what weights the user has entered as input.
 */

#include <stdio.h>
#include "simpio.h"
#include "strlib.h"
#include <string.h>

/* Constants */

#define SENTINEL_VALUE -1

/* Prototypes */

bool isMeasurable(int target, int weights[], int nWeights);

/* Main program */

main(){
	int weight, weights[10], i, j = 0, target = 0, nWeights = 0;

	for(i = 0; i < 10; i++){
		weights[i] = 0;
	}
	printf("Program by S. Wallin & A. Olausson.\n\n");
	printf("Give available weights, finish with -1\n");

	while(TRUE){
		weight = GetInteger();
		nWeights++;
		if(weight == SENTINEL_VALUE)
			break;
		else 
			weights[j] = weight;
		j++;
	}

	for(i = 0; i < 10; i++)
		target = target + weights[i];

	for (i=1; i <= target; i++){
		if(isMeasurable(i, weights, nWeights))
			printf("%d is measurable.\n", i);
		else
			printf("%d is NOT measurable.\n", i);
	}
}

/*
 * Function: isMeasurable
 * Usage: answer = isMeasurable(i, weights, nWeights);
 * -------------------------------
 * A recursive function that returns TRUE or FALSE depending if 
 * a weights is measurable. The function checks all weights up to 
 *  the maximum totalweight.
 */

bool isMeasurable(int target, int weights[], int nWeights){
	if(target == 0)
		return TRUE;
	else if(nWeights == 0)
		return FALSE;

		   isMeasurable(target - weights[nWeights - 1], weights, nWeights - 1)
		|| isMeasurable(target + weights[nWeights - 1], weights, nWeights - 1)
		|| isMeasurable(target, weights, nWeights -1);
}

